package com.study.lu;

public class 求平方根 {
    /**
     * 求X的平方根的整数部分
     * eg ： 25的平方跟为5
     * 24的平方根是4
     *
     * @param args
     */
    public static void main(String[] args) {

        System.out.println(bf(36));
        System.out.println(newton(36));

    }

    /**
     * 牛顿迭代
     *
     * @param i
     * @return
     */
    private static int newton(int i) {
        return (int) doSqart(i, i);
    }

    /**
     * x/n=n
     *
     * @param n 平方根     6
     * @param x 被求平方根数  36
     * @return
     */
    private static double doSqart(double n, int x) {
        if (x <= 0) {
            return x;
        }
        // 根据公式
        // n == (n+x/n)/2 即n是x的平方根 运算如下
        // 2n = n+x/n  双边都*n
        // 2n^2 = n^2+x
        // n^2=x
        double res = (n + x / n) / 2;
        if (res == n) {
            return res;
        } else {
            return doSqart(res, x);
        }

    }

    /**
     * 12/2  3
     *
     * @param i
     * @return
     */
    private static int bf(int i) {
        int index = -1;
        int left = 0, right = i;
        // 当两数相交即停止
        while (left <= right) {
            // int mid = left + (right - left) / 2;
            int mid = (right + left) / 2;
            // 当中间数的平方比结果小
            // 那么就要挪动左边，因为这样中间数才能变大。反之则是中间数太大了，要缩小中间数
            if (mid * mid <= i) {
                index = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }

        }

        return index;
    }
}
